//
// Created by VictorHain on 2018/8/21.
//

#ifndef GRAPH_SPARSEGRAPH_H
#define GRAPH_SPARSEGRAPH_H

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

class SparseGraph {

private:
    int n, m;
    bool directed;
    vector <vector<int>> g;
public:
    SparseGraph(int n, bool directed){
        this->n = n;
        this->m = 0;
        for (int i = 0; i < n; i++) {
            g.push_back(vector<int >());
        }
    }

    ~SparseGraph(){
    }
    int V(){ return n;}
    int E(){ return m;}

    void addEdge(int v, int w){
        assert(v >= 0 && v < n);
        assert(w >= 0 && w < n);
        if (hasEdge(v, w)){
            return;
        } else{
            g[v].push_back(w);
            if ( v != w && !directed){
                g[w].push_back(v);
            }
            m ++;
        }
    }

    bool hasEdge(int v, int w){
        assert(v >= 0 && v < n);
        assert(w >= 0 && w < n);

        for (int i = 0; i < g[v].size(); i++) {
            if (g[v][i] == w){
                return true;
            }
        }
        return false;
    }

    class AdjIterator{
    private:
        SparseGraph &G;
        int v;
        int index;
    public:
        AdjIterator(SparseGraph &graph, int v): G(graph){
            this->v = v;
            this->index = 0;
        }

        int begin(){
            if (G.g[v].size()){
                return G.g[v][0];
            }
            return -1;
        }

        int next(){
            index++;
            if (index < G.g[v].size()){
                return G.g[v][index];
            }
            return -1;
        }

        bool end(){
            return index >= G.g[v].size();
        }
    };
};


#endif //GRAPH_SPARSEGRAPH_H
